Теорема Клини

Язык регулярен тогда и только тогда, когда он распознается некоторым конечным автоматом.

Докажем, что **любой регулярный язык распознается конечным автоматом**. **План:** 1. Построить автоматы, распознающие языки $\varnothing, \{\lambda\}, \{a\}$ **(постройте самостоятельно)** 2. По ДКА $\mathcal{A}_1 = (Q_1, \Sigma, \delta_1, s_1, T_1)$ и $\mathcal{A}_2 = (Q_2, \Sigma, \delta_2, s_2, T_2)$ построить автоматы, распознающие языки: $L(\mathcal{A}_1) \cup L(\mathcal{A}_2)$, $L(\mathcal{A}_1) \cdot L(\mathcal{A}_2)$, $(L(\mathcal{A}_1))^*$. **Объединение:** Для $L(\mathcal{A}_{\cup}) = L(\mathcal{A}_1) \cup L(\mathcal{A}_2)$ автомат строится следующим образом: $$\mathcal{A}_{\cup} = (Q_1 \cup Q_2, \Sigma, \delta_1 \cup \delta_2, \{s_1, s_2\}, T_1 \cup T_2)$$ *Как получаем автомат:* Автоматы располагаются параллельно, их начальные состояния объединяются в новое множество начальных состояний НКА. **Конкатенация:** Для $L(\mathcal{A}_{\cdot}) = L(\mathcal{A}_1) \cdot L(\mathcal{A}_2)$: $$\mathcal{A}_{\cdot} = \begin{cases} (Q_1 \cup Q_2, \Sigma, \delta, \{s_1\}, T_2), & \text{при } \lambda \notin L_2 \\ (Q_1 \cup Q_2, \Sigma, \delta, \{s_1\}, T_1 \cup T_2), & \text{при } \lambda \in L_2 \end{cases}$$ где $\delta = \delta_1 \cup \delta_2 \cup \{(t, a, q) \mid t \in T_1, q \in Q_2, (s_2, a, q) \in \delta_2\}$. *Как получаем автомат:* Автоматы соединяются последовательно. Из терминальных состояний первого автомата добавляются переходы в состояния второго автомата, копирующие переходы из начального состояния второго автомата. **Замыкание Клини (Звезда):** Для $L(\mathcal{A}_{*}) = (L(\mathcal{A}_1))^*$: $$\mathcal{A}_{*} = (Q_1 \cup \{s'\}, \Sigma, \delta', \{s_1, s'\}, T \cup \{s'\})$$ где $\delta' = \delta_1 \cup \{(t, a, q) \mid t \in T, q \in Q_1, (s_1, a, q) \in \delta_1\}$. (Примечание: $s'$ нужно только для распознавания $\lambda$). *Как получаем автомат:* Добавляются переходы из терминальных состояний обратно в начальную часть автомата (аналогично переходам из стартового состояния), создавая цикл. Дополнительно вводится новое изолированное начальное состояние $s'$, являющееся терминальным, чтобы принимать пустую строку. $\square$

**Регулярность автоматных языков** Пусть $\mathcal{A} = (Q, \Sigma, \delta, s, T)$ — автомат; докажем, что $L(\mathcal{A}) \in \mathbf{R}$ индукцией по $|\delta|$. **База индукции**: $|\delta| = 0$ $L(\mathcal{A}) = \{\lambda\} \in \mathbf{R}$ при $s \in T$ и $L(\mathcal{A}) = \varnothing \in \mathbf{R}$ при $s \notin T$. **Шаг индукции**: $|\delta| = k$ По предположению индукции, языки, распознаваемые автоматами с менее чем $k$ переходами (ребрами), регулярны. Возьмем произвольный переход $(q, a, r) \in \delta$, пусть $\delta' = \delta \setminus \{(q, a, r)\}$. Положим: $\mathcal{A}_0 = (Q, \Sigma, \delta', s, T)$ $\mathcal{A}_1 = (Q, \Sigma, \delta', s, \{q\})$ $\mathcal{A}_2 = (Q, \Sigma, \delta', r, \{q\})$ $\mathcal{A}_3 = (Q, \Sigma, \delta', r, T)$ Языки $L(\mathcal{A}_0), L(\mathcal{A}_1), L(\mathcal{A}_2), L(\mathcal{A}_3)$ регулярны по предположению индукции. Докажем, что $L(\mathcal{A}) = L(\mathcal{A}_0) \cup L(\mathcal{A}_1)a(L(\mathcal{A}_2)a)^* L(\mathcal{A}_3)$. Пусть $w \in L(\mathcal{A})$ помечает $(s, t)$-маршрут $W$ в $\mathcal{A}$, $t \in T$. Если $(q, a, r) \notin W$, то $w \in L(\mathcal{A}_0)$. Если $(q, a, r) \in W$, то $w = w_0 a w_1 \dots a w_n$, где $a$ отмечают **все** случаи использования перехода $(q, a, r)$: $$s \xrightarrow{w_0} q \xrightarrow{a} r \xrightarrow{w_1} \dots \xrightarrow{w_{n-1}} q \xrightarrow{a} r \xrightarrow{w_n} t$$ Следовательно: $$w_0 \in L(\mathcal{A}_1), w_1, \dots, w_{n-1} \in L(\mathcal{A}_2), w_n \in L(\mathcal{A}_3) \Rightarrow w \in L(\mathcal{A}_1)a(L(\mathcal{A}_2)a)^* L(\mathcal{A}_3)$$ $$ \Rightarrow w \in L(\mathcal{A}_0) \cup L(\mathcal{A}_1)a(L(\mathcal{A}_2)a)^* L(\mathcal{A}_3)$$ В обратную сторону: $L(\mathcal{A}_0) \subseteq L(\mathcal{A})$ — очевидно. Если $w \in L(\mathcal{A}_1)a(L(\mathcal{A}_2)a)^* L(\mathcal{A}_3)$, то $w = w_0 a w_1 \dots a w_n$, как на рисунке выше $\Rightarrow w \in L(\mathcal{A})$. $\square$

Множество регулярных языков замкнуто относительно $\cup, \cdot, *$ и $\cap, \setminus$ и дополнение.

$$\bar{L}=\{w \in \Sigma^* \mathpunct{:} w \notin L\}$$ Если $L$ – регулярный, то $L$ распознается ДКА: $$A = (Q, \Sigma, \delta, s, T),~~ L = L(A)$$ Рассмотрим автомат с инвертированными допускающими состояниями: $$B = (Q, \Sigma, \delta, s, Q \setminus T)$$ $$w \in L(A) \iff w \notin L(B)$$ Следовательно $L(B) = \overline{L(A)} = \bar{L}$ и он является тоже регулярным, т.к. распознается ДКА. Пусть $L_1, L_2$ – регулярные. Тогда: $$L_1 \cap L_2 = \overline{\overline{L_1} \cup \overline{L_2}}$$ $$L_1 \setminus L_2 = L_1 \cap \overline{L_2}$$ $\square$